import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class Sort {

    /**
     * 直接插入排序
     *  时间复杂度:(最坏的情况)O(N^2)
     *  (最好的情况:O(N))
     *  稳定性：稳定
     *  空间复杂度O(1)
     * @param array
     */
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp=array[i];
            int j = i-1;
            for (; j >=0; j--) {
                if (array[j]>tmp){
                    array[j+1]=array[j];
                }
                else {
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }


    /**
     * 希尔排序
     * 时间复杂度: 统一理解为，O(N^1.3)~O(N^1.5)
     * 空间复杂度：O(1)
     * 稳定性:不稳定
     * @param array
     */
    public static void shellSort(int[]array){
        //首先gap等于数组长度
        int gap=array.length;
        while (gap>1){
            gap=gap/2;
            shell(array,gap);
        }
    }
    public static void shell(int[]array,int gap){
        //i++:说明是交替排序
        for (int i = gap; i < array.length; i++) {
            int tmp=array[i];
            int j = i-gap;
            for (; j >=0; j-=gap) {
                if (array[j]>tmp){
                    array[j+gap]=array[j];
                }
                else {
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }


    /**
     * 堆排序
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void heapSort(int[] array){
        //创建一个大根堆
        createHeap(array);
        int end=array.length-1;
        while (end>0){
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }
    public static void createHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >=0; parent--) {
            siftDown(array,parent,array.length);
        }
    }
    private static void siftDown(int[]array,int parent,int len){
        int child=2*parent+1;
        while (child<len){
            if (child+1<len&&array[child]<array[child+1]){
                child++;
            }
            if (array[child]>array[parent]){
                swap(array,child,parent);
            }
            else {
                break;
            }
        }
    }
    private static void swap(int[]array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    /**
     * 选择排序
     * 时间复杂度：O(N^2)
     * 空间复杂度:O(1)
     * 稳定性：不稳定
     */
    public static void selectSort(int[]array){
        for (int i = 0; i < array.length; i++) {
            int minIndex=i;
            for (int j = i+1; j < array.length; j++) {
                if (array[j]<array[minIndex]){
                    minIndex=j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    /**
     * 冒泡排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     */
    public static void bubbleSort(int[]array){
        //i:趟数
        for (int i = 0; i < array.length-1; i++) {
            boolean flg=false;
            for (int j = 0; j < array.length-1-i; j++) {
                if (array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg=true;
                }
                }
            if (!flg){
                return;
            }
        }
    }
    /**
     * 快速排序(Hoare法)
     * 时间复杂度：
     * 最好情况：O(N*logN)
     * 最坏情况：O(N^2)
     * 空间复杂度：
     * 最好情况：O(logN)
     * 最坏情况：O(N)
     * 稳定性：不稳定
     */
    public static void quickSort1(int[]array){
            quick1(array,0,array.length-1);
        }

        private static void quick1(int[] array, int start, int end) {
            //递归结束的条件
            if (start>=end){
                return;
            }
            int par=parttionHoare(array,start,end);
            quick(array,start,par-1);
            quick(array,par+1,end);
        }

        private static int parttionHoare(int[] array, int low, int high) {
            //将low下标的值，作为基准值存下来
            int pivot=array[low];
            int i=low;
            while (low<high){
                while (low<high&&array[high]>=pivot){
                    high--;
                }
                while (low<high&&array[low]<=pivot){
                    low++;
                }
                swap(array,low,high);
            }
            swap(array,i,low);
            return low;
    }
    /**
     * 快速排序(挖坑法)
     */
    public static void quickSort(int[]array){
        quick(array,0,array.length-1);
    }

    private static void quick(int[] array, int start, int end) {
        //递归结束的条件
        if (start>=end){
            return;
        }
        int par=parttion(array,start,end);
        quick(array,start,par-1);
        quick(array,par+1,end);
    }

    private static int parttion(int[] array, int low, int high) {
        int tmp=array[low];
        while (low<high){
            while (low<high&&array[high]>=tmp){
                high--;
            }
            array[low]=array[high];
            while (low<high&&array[low]<=tmp){
                low++;
            }
            array[high]=array[low];
        }
       array[low]=tmp;
        return low;
    }
    /**
     * 快速排序(三数取中法)->优化版本
     */
    public static void quickSort2(int[]array){
        quick1(array,0,array.length-1);
    }

    private static void quick2(int[] array, int start, int end) {
        //递归结束的条件
        if (start>=end){
            return;
        }
        //采用三数取中法，找到中间下标，然后将中间下标和start下标的值交换
        int index=threeMid(array,start,end);
        swap(array,start,index);
        int par=parttionHoare1(array,start,end);
        quick(array,start,par-1);
        quick(array,par+1,end);
    }

    private static int threeMid(int[] array, int low, int high) {
        int mid=(low+high)/2;
        if (array[low]<array[high]){
            if (array[mid]<array[low]){
                return low;
            }else if(array[mid]>array[high]){
                return high;
            }else {
                return mid;
            }
        }
        else {
            if (array[mid]<array[high]){
                return high;
            }else if(array[mid]>array[low]){
                return low;
            }else {
                return mid;
            }
        }
    }

    private static int parttionHoare1(int[] array, int low, int high) {
        //将low下标的值，作为基准值存下来
        int pivot=array[low];
        int i=low;
        while (low<high){
            while (low<high&&array[high]>=pivot){
                high--;
            }
            while (low<high&&array[low]<=pivot){
                low++;
            }
            swap(array,low,high);
        }
        swap(array,i,low);
        return low;
    }
    /**
     * 快速排序(非递归写法)
     */
    public static void quickSortNor(int[]array){
        int start=0;
        int end=array.length-1;
        int par=parttion(array,start,end);
        //创建一个栈
        Deque<Integer> stack=new LinkedList<>();
        //判断左边是否至少有2个元素
        if (par>start+1){
            stack.push(start);
            stack.push(par-1);
        }
        //判断右边是否至少有2个元素
        if (par<end-1){
            stack.push(par+1);
            stack.push(end);
        }
        //判断栈是否为空，不为空就弹出栈顶的2个元素，让弹出的第一个元素等于end,弹出的第二个元素等于start,再次调用parttion,找到新的par,再接着去
        //判断par的左边和右边是否至少有2个元素
        while (!stack.isEmpty()){
            end=stack.pop();
            start=stack.pop();
            par=parttion(array,start,end);
            //判断左边是否至少有2个元素
            if (par>start+1){
                stack.push(start);
                stack.push(par-1);
            }
            //判断右边是否至少有2个元素
            if (par<end-1){
                stack.push(par+1);
                stack.push(end);
            }
        }
    }
    /**
     * 归并排序(递归形式)
     * 时间复杂度:O(n*logN)
     * 空间复杂度:O(N)
     * 稳定性：稳定
     */
    public static void mergeSort(int[]array){
        mergeSortChild(array,0,array.length-1);
    }

    private static void mergeSortChild(int[] array, int left, int right) {
        //递归结束的条件
        if (left>=right){
            return;
        }
        int mid=(left+right)/2;
        mergeSortChild(array,left,mid);
        mergeSortChild(array,mid+1,right);
        //归并
        merge(array,left,mid,right);
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int [] tmp=new int[right-left+1];
        int k=0;
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        while (s1<=e1&&s2<=e2){
            if (array[s1]<=array[s2]){
                tmp[k++]=array[s1++];
            }else {
                tmp[k++]=array[s2++];
            }
        }
        while (s1<=e1){
            tmp[k++]=array[s1++];
        }
        while (s2<=e2){
            tmp[k++]=array[s2++];
        }
        //把tmp数组里面的数据拷回array数组里面
        for (int i = 0; i < tmp.length; i++) {
            array[i+left]=tmp[i];
        }
    }
    /**
     * 归并排序(非递归的形式)
     */
    public static void mergeSortNor(int[]array){
        int gap=1;
        while (gap<array.length){
            for (int i = 0; i < array.length; i=i+2*gap) {
                int left=i;
                 int mid=left+gap-1;
                 if (mid>=array.length){
                     mid=array.length-1;
                 }
                 int right=mid+gap;
                 if (right>=array.length){
                     right=array.length-1;
                 }
                 merge(array,left,mid,right);
            }
            gap*=2;
        }
    }
    /**
     * 计数排序
     * 时间复杂度：O(N+范围)
     * 空间复杂度：O(范围)
     * 稳定性：
     */
    public static void countSort(int[]array){
        //找array数组里的最大值，最小值O(N)
        int max=array[0];
        int min=array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i]>max){
                max=array[i];
            }
            if (array[i]<min){
                min=array[i];
            }
        }
        //创建一个计数数组count
        int range=max-min+1;
        int []count=new int[range];
        //遍历array数组，开始计数O(N)
        for (int i = 0; i < array.length; i++) {
            int index=array[i];
            count[index-min]++;
        }
        //遍历count数组O(范围)
        int k=0;
        for (int i = 0; i < count.length; i++) {
            while (count[i]!=0){
                array[k]=i+min;
                count[i]--;
                k++;
            }
        }
    }
}

